//import java.io.*;
//import java.util.*;
//
//public class BFSAlgorithm {
//
//    private Graph graph;
//
//    /**
//     * Constructor.
//     */
//    public BFSAlgorithm(Graph g) {
//        graph = g;
//    }
//
//    /**
//     * 1 - Create a stack to store all the vertices of our path on.
//     * 2 - First push the 'end' vertex on our stack.
//     * 3 - Now loop from the highest level back to the first level and
//     *     a. loop through each level and
//     *     b. check each vertex in that level if it's connected to the
//     *        vertex on the top of our stack, if we find a match, push that
//     *        match on the stack and break out of the loop.
//     * 4 - Now we only need to reverse the collection (stack) before returning
//     *     the path in the "correct" order (from start to finish).
//     *
//     * Here's an example ASCII drawing of backtracking from the end vertex "n"
//     * to the starting vertex "g". The arrows, <-, denote the path that was
//     * found.
//     *
//     * level:  0      1      2      3       4      5      6    7     8
//     *        ---------------------------------------------------------
//     *         g <-+  IV     e      I       a   +- III <- o <- VI <- n
//     *             +- V <-+  f   +- II <-+  b   |         p
//     *                    +- c <-+       |  d   |
//     *                       j           +- h <-+
//     *                                      q
//     *                                      r
//     */
//    private List<String> backTrack(List<List<String>> container, String end) {
//        Stack<String> path = new Stack<String>();                     // 1
//        path.push(end);                                               // 2
//        for(int i = container.size()-1; i >= 0; i--) {                // 3
//            List<String> level = container.get(i);
//            String last = path.peek();
//            for(String s : level) {                                   // a
//                if(graph.areConnected(last, s)) {                     // b
//                    path.push(s);
//                    break;
//                }
//            }
//        }
//        Collections.reverse(path);                                    // 4
//        return path;
//    }
//
//    /**
//     * 1 - Get the level from the 'container' which was added last.
//     * 2 - Create a new level to store (possible) unexplored verices in.
//     * 3 - Loop through each of the vertices from the last added level, and
//     *     a. get the neighboring vertices connected to each vertex,
//     *     b. loop through each connecting vertex and if the connecting vertex
//     *        has not yet been visited,
//     *     c. only then add it to the newly created level-list and mark it as
//     *        visited in our set.
//     * 4 - We don't need to search any further if we stumble upon the 'end'
//     *     vertex. In that case, just "return" from this method.
//     * 5 - Only make the recursive call if we have found vertices which have
//     *     not been explored yet.
//     */
//    private void bfs(List<List<String>> container,
//            String end, Set<String> visited) {
//
//        List<String> lastLevel = container.get(container.size()-1);   // 1
//        List<String> newLevel = new ArrayList<String>();              // 2
//
//        for(String vertex : lastLevel) {                              // 3
//            List<String> edges = graph.getEdges(vertex);              // a
//            for(String edge : edges) {                                // b
//                if(!visited.contains(edge)) {                         // c
//                    visited.add(edge);
//                    newLevel.add(edge);
//                }
//                if(edge.equals(end)) return;                          // 4
//            }
//        }
//        if(newLevel.size() > 0) {                                     // 5
//            container.add(newLevel);
//            bfs(container, end, visited);
//        }
//    }
//
//    /**
//     * 1 - Create an empty 'container' to store all the levels from the
//     *     'start'-vertex in. A level is also a list with one or more vertices.
//     * 2 - The first level only holds the 'start' vertex, which is added first,
//     *     this is the 'init' list.
//     * 3 - The 'start' vertex is also stored in a Set which keeps track of all
//     *     the vertices we have encountered so that we don't traverse vertices
//     *     twice (or more).
//     * 4 - Once we initialized the steps 1-3, we can call the actual BFS-
//     *     algorithm.
//     * 5 - Once the BFS-algorithm is done, we call the backTrack(...) method
//     *     to find the shortest path between 'end' and 'start' between the
//     *     explored levels of the graph.
//     */
//    public List<String> getShortestPath(String start, String end) {
//        List<List<String>> container = new ArrayList<List<String>>(); // 1
//        List<String> init = new ArrayList<String>();                  // 2
//        init.add(start);
//        container.add(init);
//        Set<String> visited = new HashSet<String>();                  // 3
//        visited.add(start);
//        bfs(container, end, visited);                                 // 4
//        return backTrack(container, end);                             // 5
//    }
//
//    /**
//     * Main method:
//     *  1 - Create a Graph.
//     *  2 - Get a shortest path between two vertices.
//     *  3 - Print the shortest path.
//     */
//    public static void main(String[] args) throws FileNotFoundException {
//        Graph graph = new Graph("data.txt");                          // 1
//        BFSAlgorithm bfsAlgorithm = new BFSAlgorithm(graph);
//        List<String> shortestPath =
//            bfsAlgorithm.getShortestPath("g", "n");                   // 2
//        for(int i = 0; i < shortestPath.size(); i++) {
//            System.out.print(shortestPath.get(i));                    // 3
//            System.out.print(i < shortestPath.size()-1 ? "\n -> " : "\n");
//        }
//    }
//}
//